package algorithm;

/**
 * 给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
 */
public class T00402 {
    public static void main(String[] args) {
        System.out.println(new Solution().removeKdigits("1432219", 3));
    }

static class Solution {
    public String removeKdigits(String num, int k) {
        if(k <= 0)
            return num;
        if(num == null || num.length() == 0 || k >= num.length())
            return "0";
        final char[] numArr = num.toCharArray();
        char[] stack = new char[numArr.length];
        int si = 0, index = 0;
        for (int i = 0; i < k; i++) {
            for(;index < numArr.length;) {
                if(si == 0)
                    stack[si ++] = numArr[index ++];
                else if(stack[si - 1] > numArr[index]) {
                    si--;
                    break;
                } else
                    stack[si ++] = numArr[index ++];
            }
        }
        char[] resArr = new char[numArr.length - k];
        int resIndex = 0;
        for (int i = 0; i < si && resIndex < resArr.length; i++, resIndex ++) {
            resArr[resIndex] = stack[i];
        }
        while(resIndex < resArr.length && index < numArr.length)
            resArr[resIndex ++] = numArr[index ++];

        int start = 0;
        for(int i = 0; i < resArr.length; i++) {
            if(resArr[i] == '0')
                start ++;
            else
                break;
        }
        if(start == resArr.length)
            return "0";
        return new String(resArr, start, resArr.length - start);
    }
}
}